package MyLinkedList;
/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2021-11-03
 * Time:6:05
 */
//ListNode代表一个节点
class ListNode {
    public int val;
    public ListNode next;//null

    public ListNode(int val) {
        this.val = val;
    }
}

public class myLinkedList {

    public ListNode head;//链表的头引用

    public void createList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        //stNode5.next = null;
        this.head = listNode1;
    }

    public void display() {
        //this.head.next != null
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }


    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
        /*if(this.head == null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }*/
    }

    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head==null){
            this.head=node;
        }else{
            ListNode cur = this.head;
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
        //当链表为空时，尾插之后，head仍为空，造成错误
//        ListNode cur = this.head;
//        while (cur!=null && cur.next!=null){
//            cur=cur.next;
//        }
//        ListNode node = new ListNode(data);
//        cur.next=node;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        return false;
    }

    public ListNode searchPerv(int key){
        ListNode cur = this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null) {
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPerv(key);
        if(cur==null){
            System.out.println("找不到你要删除的节点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

//    //删除第一次出现关键字为key的节点
//    public void remove(int key){
//        if(this.head == null) {
//            System.out.println("单链表为空，不能删除！");
//            return;
//        }
//        if(this.head.val == key) {//key的节点为头节点
//            this.head = this.head.next;
//            return;
//        }
//        ListNode cur = this.head;
//        while (cur.next!=null){
//            if(cur.next.val==key){
//                ListNode del = cur.next;
//                cur.next = del.next;
//            }
//            cur=cur.next;
//            return;
//        }
//        System.out.println("找不到关键字为"+key+"的节点");
//    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head==null){
            System.out.println("链表为空，没有可删除的节点！");
            return;
        }
        ListNode curPrev = head;
        ListNode cur = curPrev.next;
        while(cur!=null){
            if(cur.val==key){
                curPrev.next=cur.next;
                cur=cur.next;
            }else {
                cur=cur.next;
                curPrev=curPrev.next;
            }
        }
        if (head.val==key){
            head=head.next;
        }
    }

    //反转一个单链表
    public ListNode reverse(ListNode head){
        if(head==null){
            return null;
        }
        ListNode cur = head;
        ListNode prev = null;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    //返回链表的中间结点
    public ListNode middleNode(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //输入一个链表，输出该链表中倒数第k个结点。
    public ListNode FindKthToTail(ListNode head,int k){
        if(head==null||k<=0){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k-1; i++) {
            fast = fast.next;
            if (fast==null){
                return null;
            }
        }
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode node = head;
        while(l1!=null||l2!=null){
            if(l1!=null&&l2!=null){
                if (l1.val>l2.val){
                    node.next = l2;
                    l2 = l2.next;
                }else{
                    node.next = l1;
                    l1 = l1.next;
                }
                node = node.next;
            }else if (l1==null){
                node.next = l2;
                break;
            }else {
                node.next = l1;
                break;
            }
        }
        return head.next;
    }

    //编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

//    public ListNode partition(int x) {
//        // write code here
//        ListNode bs = null;
//        ListNode be = null;
//        ListNode as = null;
//        ListNode ae = null;
//        ListNode cur = head;
//        while (cur != null) {
//            if(cur.val < x) {
//                //1、第一次
//                if(bs == null) {
//                    bs = cur;
//                    be = cur;
//                }else {
//                    //2、不是第一次  尾插
//                    be.next = cur;
//                    be = be.next;
//                }
//            }else {
//                if(as == null) {
//                    as = cur;
//                    ae = cur;
//                }else {
//                    //2、不是第一次
//                    ae.next = cur;
//                    ae = ae.next;
//                }
//            }
//            cur = cur.next;
//        }
//        //预防第一个段为空
//        if(bs == null) {
//            return as;
//        }
//        be.next = as;
//        //预防第2个段当中的数据，最后一个节点不是空的
//        if(as != null) {
//            ae.next = null;
//        }
//        return bs;
//    }


    public ListNode partition(int key){
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur!=null){
            if(cur.val<key){
                if(bs==null){//第一次
                    bs = cur;
                    be = cur;
                }else {//不是第一次 尾插
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if(as==null){//第一次
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //所有数据都大于key
        if(bs==null){
            return as;
        }
        be.next = as;
        if(as!=null){//最后一个数据小于key，则ae.next不是null，需要手动置为null
            ae.next = null;
        }
        return bs;
    }

    //没过的用例
//    public ListNode partition(ListNode head, int key) {
//        if(head==null){
//            return null;
//        }
//        ListNode prev = new ListNode(-1);
//        ListNode curPre = prev;
//        ListNode after = new ListNode(-2);
//        ListNode curAft = after;
//        while(head!=null){
//            if(head.val<key){
//                curPre.next = head;
//                head = head.next;
//                curPre = curPre.next;
//            }else{
//                curAft.next = head;
//                head = head.next;
//                curAft = curAft.next;
//            }
//        }
//        curAft = null;
//        curPre = after.next;
//        return prev.next;
//    }


    //删除链表重复节点 连续的
    public ListNode deleteDuplication() {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(head!=null){
            if(head.next!=null && head.val==head.next.val){
                while(head.next!=null && head.val==head.next.val){//判断两个及以上连续重复的节点
                    head = head.next;
                }
                head = head.next;
            }else {
                tmp.next = head;
                head = head.next;
                tmp = tmp.next;
            }
        }
        tmp.next = null;//最后一个节点需要手动置空
        return newHead.next;
    }

    //判断链表是否有环
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

    //*链表开始入环的第一个节点
    public ListNode detectCycle() {
        if(head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                fast = head;
                while (fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }

    //输入两个链表，找出它们的第一个公共结点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        ListNode pl = headA;
        ListNode ps = headB;
        int l = 0;
        int s = 0;
        int count = 0;
        while(pl!=null) {
            pl = pl.next;
            l++;
        }
        while (ps!=null){
            ps = ps.next;
            s++;
        }
        if(l<s){
            pl = headB;
            ps = headA;
            count = s-l;
        }else {
            pl = headA;
            ps = headB;
            count = l-s;
        }
        while(count!=0){
            pl = pl.next;
            count--;
        }
        while(pl!=null){
            if(pl==ps){
                return pl;
            }
            pl = pl.next;
            ps = ps.next;
        }
        return null;
    }

    //输入两个链表，找出它们的第一个公共结点
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        int countA = 0;
        int countB = 0;
        while(curA!=null){
            curA = curA.next;
            countA++;
            curB = curB.next;
        }
        while(curB!=null){
            curB = curB.next;
            countB++;
        }
        curB = headB;
        curA = headA;
        if(countB>countA){
            while((countB-countA)!=0){
                curB = curB.next;
                countB--;
            }
            while(curB!=null || curA!=null){
                if(curB.next == curA.next){
                    return curB.next;
                }
                curB = curB.next;
                curA = curA.next;
            }
        }
        if(countA>countB){
            while((countA-countB)!=0){
                curA = curA.next;
                countA--;
            }
            while(curB!=null || curA!=null){
                if(curB.next == curA.next){
                    return curB.next;
                }
                curB = curB.next;
                curA = curA.next;
            }
        }
        return null;
    }

    //链表的回文结构
    public boolean chkPalindrome() {
        if(head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        //找到中间
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转后半段
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //判断回纹
        while(head!=slow && head.next!=slow){
            if(head.val==slow.val){
                head = head.next;
                slow = slow.next;
            }else{
                return false;
            }
        }
        return true;
    }

    public void clear(){

    }

}